#define _CRT_SECURE_NO_WARNINGS
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

struct ListNode* partition(struct ListNode* pHead, int x) {
    struct ListNode* smallhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* bighead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* smalltail = smallhead;
    smalltail->next = NULL;
    struct ListNode* bigtail = bighead;
    bigtail->next = NULL;

    struct ListNode* cur = pHead;
    while (cur) {
        if (cur->val < x)
        {
            smalltail->next = cur;
            smalltail = cur;
        }
        else
        {
            bigtail->next = cur;
            bigtail = cur;
        }
        cur = cur->next;
    }
    smalltail->next = bighead->next;
    bigtail->next = NULL;

    pHead = smallhead->next;
    free(smallhead);
    free(bighead);
    return pHead;
}
